# -*- coding: utf-8 -*-

"""740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4"""

from collections import Counter

class Solution:
    """
    -------------------------------------------------------------------------
    递归基础：
        f({}) = 0    # 当没有顶点的时候，无点可取，获得点数为0
    递归定义：
        f(G) = max(
                f(G - {b, a,a,a,...,a, c,c,c,...,c}) + b
                , f(G - {m, l,l,l,...,l, n,n,n,...,n}) + m
                , f(G - {y, x,x,x,...,x, z,z,z,...,z}) + y
                ,...
                )

    抽象成图，{1, 2}, {2, 3}是具有的相邻关系为无向边，值相同的数在图上有多个点，只是这些相同点邻接关系具有对称性。
    每次从图中取一个点 3，都能将其邻接的点（所有2和所有4）一并删除，剩下一个子图。
    按递归定义，当前图能取得最大点数，等于（各子图能取得最大点数+各子图对应取法点数之和）的最大值。

    如果按动态规划来做，将递归计算转换为递推的状态缓存，过程有点复杂。先采用递归计算结合计算结果备份的方式来实现一下。
    -------------------------------------------------------------------------
    改进机会：如果取到 x，那么顺势将 x-1，x+1 取完，因为 x-1,x+1 是所有 x 的共同邻接顶点，那么剩下的其余 x 就是孤立的顶点，在其子图中也就只能逐渐把 x 挨个取完。
    改进策略：取到 x，将后续子图中逐步取剩余的 x 子图收上来，相当于是将 x，x-1，x+1 全部取完的子图。
        f(G) = max(
                f(G - {b, a,a,a,...,a, c,c,c,...,c, b,b,b,...,b}) + b*count
                , f(G - {m, l,l,l,...,l, n,n,n,...,n, m,m,m,...,m}) + m*count
                , f(G - {y, x,x,x,...,x, z,z,z,...,z, y,y,y,...,y}) + y*count
                ,...
                )
    -------------------------------------------------------------------------
    还是超时，再来优化，既然已经将连续的3个值节点全部取出，只用中间点结算，那么就可以将图模型压缩到按值 从小到大的顺序结构 。
    示例：
        nums = {1:20, 2:6, 3:5, 4:17, 5:8, 6:7, 7:6, 8:11, 9:8, 10:12}

        | 1️⃣ | 2️⃣ | 3️⃣ | 4️⃣ | 5️⃣ | 6️⃣ | 7️⃣ | 8️⃣ | 9️⃣ | 🔟 | 取值
        | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | 🔟
        | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | ❌ | 9️⃣
        | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | ❌ | ✔️ | 8️⃣
        | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | ❌ | ✔️ | ✔️ | 7️⃣
        | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | 6️⃣
        | ✔️ | ✔️ | ✔️ | ❌ | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | ✔️ | 5️⃣
        | ✔️ | ✔️ | ❌ | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | 4️⃣
        | ✔️ | ❌ | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | 3️⃣
        | ❌ | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | 2️⃣
        | ⭕ | ❌ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | 1️⃣

        每行分别代表取⭕ 1,2,3,...10 的时候，剩下的序列✔️，求值就是对每行先计算，再返回最大的结果。
        仔细观察这10种取值情况，里面蕴涵着偏序关系的所有可能：定义get(v)为取v的情况下，能获得的最大结果
        get(8) 一定小于等于 get(10)
        get(7) 要么小于等于 get(9)，要么小于等于 get(10)
        get(6) 要么小于等于 get(8)，要么小于等于 get(9)
        get(5) 要么小于等于 get(7)，要么小于等于 get(8)
        get(4) 要么小于等于 get(6)，要么小于等于 get(7)
        get(3) 要么小于等于 get(5)，要么小于等于 get(6)
        get(2) 要么小于等于 get(4)，要么小于等于 get(5)
        get(2) 要么小于等于 get(3)，要么小于等于 get(4)
        所以，get(10), get(9) 是这些情况的极大值。（画成偏序图更直观）

    定义 f(v) 为从 值头 到 值v 的最大结果，并且将序列中没有的值占位，当成 0 个处理。
    递归基础：
        f(vhead) = vhead * count(vhead)                                                                 # 截至 头值 的最大
        f(vhead1) = max(vhead1 * count(vhead1), vhead * count(vhead))                                   # 截至 头值+1 的最大
        f(vhead11) = max(vhead * count(vhead) + vhead11 * count(vhead11), vhead1 * count(vhead1))       # 截至 头值+1+1 的最大
    递归定义：
        f(v) = max( f(v-2) + v*count(v), f(v-3) + (v-1)*count(v-1) )
    将这个顺序模型按动态规划，将递归转换为递推，状态缓存。
    -------------------------------------------------------------------------
    换个角度，这是不是就是相邻劫舍问题？实际上最后的优化是受到相邻劫舍问题的启发，试图在不同的取值情况种试图找到一种偏序结构，也算是一种解释。
    """
    def deleteAndEarnSlow(self, nums: list) -> int:
        nums = Counter(nums)

        def stringfy(G):
            keys = list(G.keys())
            keys.sort()
            return ','.join(['%d:%d' % (k, G[k]) for k in keys])

        backup = dict()

        def recursive(G:Counter):
            maxEarn = 0
            for x in G:
                subG = G.copy()
                # 取走一个节点
                if subG[x] == 1:
                    del subG[x]
                else:
                    subG[x] -= 1
                # 顺势取走所有相邻节点
                try:
                    del subG[x-1]
                except KeyError:
                    pass
                try:
                    del subG[x+1]
                except KeyError:
                    pass

                print(x, subG)

                subG_text = stringfy(subG)
                if subG_text in backup:
                    max_subG = backup[subG_text]
                else:
                    max_subG = recursive(subG)
                    backup[subG_text] = max_subG

                maxEarn = max(max_subG+x, maxEarn)
            return maxEarn

        return recursive(nums)

    def deleteAndEarnG(self, nums: list) -> int:
        nums = Counter(nums)

        def stringfy(G):
            keys = list(G.keys())
            keys.sort()
            return ','.join([str(k) for k in keys])

        backup = dict()

        def recursive(G:Counter):
            maxEarn = 0
            for x in G:
                subG = G.copy()

                x_earn = x*subG[x]

                # 取走x的所有节点
                del subG[x]

                # 顺势取走所有相邻节点
                try:
                    del subG[x-1]
                except KeyError:
                    pass
                try:
                    del subG[x+1]
                except KeyError:
                    pass

                # print(x, subG)

                subG_keys = stringfy(subG)
                if subG_keys in backup:
                    max_subG = backup[subG_keys]
                else:
                    max_subG = recursive(subG)
                    backup[subG_keys] = max_subG

                if stringfy(G) == '1,2,3,4,5,6,7,8,9,10':
                    print(x, subG_keys, max_subG+x_earn)

                maxEarn = max(max_subG+x_earn, maxEarn)
            return maxEarn

        return recursive(nums)

    @staticmethod
    def pretty(G):
        keys = list(G.keys())
        keys.sort()
        return ','.join(['%d:%d' % (k, G[k]) for k in keys])

    def deleteAndEarn(self, nums: list) -> int:
        nums = Counter(nums)
        # print(self.pretty(nums))
        vhead, vtail = min(nums.keys()), max(nums.keys())
        # print(vhead, vtail)

        dp_vhead1, dp_vhead2, dp_vhead3 = vhead * nums.get(vhead, 0)\
            , max((vhead+1) * nums.get(vhead+1, 0), vhead * nums.get(vhead, 0))\
            , max(vhead * nums.get(vhead, 0) + (vhead+2) * nums.get(vhead+2, 0), (vhead+1) * nums.get(vhead+1, 0))\

        # print(dp_vhead1, dp_vhead2, dp_vhead3)
        
        size = vtail-vhead
        if size == 0:
            return dp_vhead1
        elif size == 1:
            return dp_vhead2
        elif size == 2:
            return dp_vhead3

        dp_vhead4 = 0

        v = vhead+3
        while v <= vtail:
            dp_vhead4 = max(dp_vhead2+v*nums.get(v, 0), dp_vhead1+(v-1)*nums.get(v-1, 0))
            # print(v, dp_vhead1, dp_vhead2, dp_vhead3, dp_vhead4)
            dp_vhead1, dp_vhead2, dp_vhead3 = dp_vhead2, dp_vhead3, dp_vhead4
            v += 1

        return dp_vhead4

if __name__ == '__main__':
    # fp = open('./g.log', 'w')
    # fp.write('')
    # fp.close()
    # fp = open('./g.log', 'a')
    print(Solution().deleteAndEarn([12,32,93,17,100,72,40,71,37,92,58,34,29,78,11,84,77,90,92,35,12,5,27,92,91,23,65,91,85,14,42,28,80,85,38,71,62,82,66,3,33,33,55,60,48,78,63,11,20,51,78,42,37,21,100,13,60,57,91,53,49,15,45,19,51,2,96,22,32,2,46,62,58,11,29,6,74,38,70,97,4,22,76,19,1,90,63,55,64,44,90,51,36,16,65,95,64,59,53,93]))
    # fp.close()
